This invention relates to high-performance 3-D graphics imaging. More particularly, the invention relates to geometry operations in a 3D-graphics pipeline, operations such as transformations, clippings, decompositions and lighting calculations.
Three-Dimensional Computer Graphics
Computer graphics is the art and science of generating pictures with a computer. Generation of pictures, or images, is commonly called rendering. Generally, in three-dimensional (3D) computer graphics, geometry that represents surfaces (or volumes) of objects in a scene is translated into pixels stored in a framebuffer and then displayed on a display device.
In a 3D animation, a sequence of still images is displayed, giving the illusion of motion in three-dimensional space. Interactive 3D computer graphics allows a user to change his viewpoint or change the geometry in real-time, thereby requiring the rendering system to create new images on the fly in real time.
In 3D computer graphics, each renderable object generally has its own local object coordinate system and, therefore, needs to be translated (or transformed) from object coordinates to pixel-display coordinates. Conceptually, this translation is a four-step process: 1) translation from object coordinates to world coordinates, the coordinate system for the entire scene, 2) translation from world coordinates to eye coordinates, based on the viewing point of the scene, 3) translation from eye coordinates to perspective-translated eye coordinates and 4) translation from perspective-translated eye coordinates to pixel (screen) coordinates. These translation steps can be compressed into one or two steps by pre-computing appropriate translation matrices before any translation occurs.
(Translation from object coordinates includes scaling for size enlargement or shrink. Perspective scaling makes farther objects appear smaller. Pixel coordinates are points in three-dimensional space in either screen precision (that is to say, pixels) or object precision (that is to say, high-precision numbers, usually floating-point).
Once the geometry is in screen coordinates, it is broken into a set of pixel-color values (that is, xe2x80x9crasterizedxe2x80x9d) that are stored into the framebuffer.
A summary of the prior-art rendering process can be found in Watt, Fundamentals of Three-dimensional Computer Graphics (Addison-Wesley Publishing Company, 1989, reprinted 1991, ISBN 0-201-15442-0, herein xe2x80x9cWattxe2x80x9d and incorporated by reference), particularly Chapter 5, xe2x80x9cThe Rendering Process,xe2x80x9d pages 97 to 113, and Foley et al., Computer Graphics: Principles and Practice, 2nd edition (Addison-Wesley Publishing Company, 1990, reprinted with corrections 1991, ISBN 0-201-12110-7, herein xe2x80x9cFoley et al.xe2x80x9d and incorporated by reference).
FIG. 1 shows a three-dimensional object, a tetrahedron, with its own coordinate axes (xobject, yobject, zobject). The three-dimensional object is translated, scaled and placed in the viewing point""s coordinate system based on (xeye, yeye, zeye). The object is projected onto the viewing plane, thereby correcting for perspective. At this point, the object appears to have become two-dimensional. The object""s z-coordinates, however, are preserved for later use in hidden-surface removal. The object is finally translated to screen coordinates, based on (xscreen, yscreen, zscreen), where zscreen is going perpendicularly into the page. Points on the object now have their x and y coordinates described by pixel location (and fractions thereof) within the display screen and their z coordinates in a scaled version of distance from the viewing point.
Generic 3D-Graphics Pipeline
Many hardware renderers have been developed. See, for example, Deering et al., xe2x80x9cLeo: A System for Cost Effective 3D Shaded Graphics,xe2x80x9d SIGGRAPH93 Proceedings, Aug. 1-6, 1993, Computer Graphics Proceedings, Annual Conference Series (ACM SIGGRAPH, 1993, Soft-cover ISBN 0-201-58889-7 and CD-ROM ISBN 0-201-56997-3, herein xe2x80x9cDeering et al.xe2x80x9d and incorporated by reference), particularly at pages 101 to 108. Deering et al. includes a diagram of a generic 3D-graphics pipeline (that is to say, a renderer, or a rendering system) that it describes as xe2x80x9ctruly generic, as at the top level nearly every commercial 3D graphics accelerator fits this abstraction.xe2x80x9d This pipeline diagram is reproduced here as FIG. 6. (In this figure, the blocks with rounded corners typically represent functions or process operations, while sharp-cornered rectangles typically represent stored data or memory.)
Such pipeline diagrams convey the process of rendering but do not describe any particular hardware. This document presents a new graphics pipeline that shares some of the steps of the generic 3D-graphics pipeline. Each of the steps in the generic 3D-graphics pipeline is briefly explained here. (Processing of polygons is assumed throughout this document, but other methods for describing 3D geometry could be substituted. For simplicity of explanation, triangles are used as the type of polygon in the described methods.)
As seen in FIG. 6, the first step within the floating point-intensive functions of the generic 3D-graphics pipeline after the data input (step 612) is the transformation step (step 614), described above. The transformation step also includes xe2x80x9cget next polygon.xe2x80x9d
The second step, the clip test, checks the polygon to see if it is at least partially contained in the view volume (sometimes shaped as a frustum) (step 616). If the polygon is not in the view volume, it is discarded. Otherwise, processing continues.
The third step is face determination, where polygons facing away from the viewing point are discarded (step 618). Generally, face determination is applied only to objects that are closed volumes.
The fourth step, lighting computation, generally includes the set up for Gouraud shading and/or texture mapping with multiple light sources of various types but could also be set up for Phong shading or one of many other choices (step 622).
The fifth step, clipping, deletes any portion of the polygon that is outside of the view volume because that portion would not project within the rectangular area of the viewing plane (step 624). Conventionally, coordinates including color texture coordinates must be created for each new primative. Polygon clipping is computationally expensive.
The sixth step, perspective divide, does perspective correction for the projection of objects onto the viewing plane (step 626). At this point, the points representing vertices of polygons are converted to pixel-space coordinates by step seven, the screen space conversion step (step 628).
The eighth step (step 632), set up for an incremental render, computes the various begin, end and increment values needed for edge walking and span interpolation (e.g.: x, y and z coordinates, RGB color, texture map space, u and v coordinates and the like).
Within the drawing-intensive functions, edge walking (step 634) incrementally generates horizontal spans for each raster line of the display device by incrementing values from the previously generated span (in the same polygon), thereby xe2x80x9cwalkingxe2x80x9d vertically along opposite edges of the polygon. Similarly, span interpolation (step 636) xe2x80x9cwalksxe2x80x9d horizontally along a span to generate pixel values, including a z-coordinate value indicating the pixel""s distance from the viewing point. Finally, the z-test and/or alpha blending (also referred to as Testing and Blending) (step 638) generates a final pixel-color value. The pixel values also include color values, which can be generated by simple Gouraud shading (that is to say, interpolation of vertex-color values) or by more computationally expensive techniques such as texture mapping (possibly using multiple texture maps blended together), Phong shading (that is to say, per-fragment lighting) and/or bump mapping (perturbing the interpolated surface normal).
After drawing-intensive functions are completed, a double-buffered MUX output look-up table operation is performed (step 644). The generic 3D-graphics pipeline includes a double-buffered framebuffer, so a double-buffered MUX is also included. An output lookup table is included for translating color-map values.
By comparing the generated z-coordinate value to the corresponding value stored in the Z Buffer, the Z-test either keeps the new pixel values (if it is closer to the viewing point than previously stored value for that pixel location) by writing it into the framebuffer or discards the new pixel values (if it is farther).
At this step, antialiasing methods can blend the new pixel color with the old pixel color. The z-buffered blend generally includes most of the per-fragment operations, described below.
Finally, digital-to-analog conversion makes an analog signal for input to the display device.
The language of the OpenGL API is adopted, except as contraindicated herein. (See, for example, Open Architecture Review Board, OpenGL Reference Manual, 2nd edition (Addison-Wesley Developers Press, 1996) and OpenGL Architecture Review Board, OpenGL Programming Guide, 2nd edition (Addison-Wesley, 1997), both incorporated herein by reference.
These and other goals of the invention will be readily apparent to one of skill in the art on reading the background above and the description below.
Herein are described apparatus and methods for rendering 3D-graphics images. In one embodiment, the apparatus include a port for receiving commands from a graphics application, an output for sending a rendered image to a display and a geometry-operations pipeline, coupled to the port and to the output, the geometry-operations pipeline including a block for performing transformations.
In one embodiment, the block for performing transformations includes a co-extensive logical and first physical stages, as well as a second physical stage including multiple logical stages. The second physical stage includes multiple logical stages that interleave their execution.